﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.SemiRings;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Schemes.DynamicProgramming;
using Algoritmia.Utils;

namespace Algoritmia.Problems.GeneralizedCoinChange.ByScheme
{
    public class BackwardsWithDecisionCoinChanger
    {
        private readonly DataStructures.Lists.IList<int> _values;
        private readonly Func<int, int, ValueWithDecisionAndBackpointer<double, int>> _weightingFunction;
        private readonly IterativeIdempotentDynamicProgrammingSolver<int, int, ValueWithDecisionAndBackpointer<double,int>> _solver;

         public BackwardsWithDecisionCoinChanger(DataStructures.Lists.IList<int> values, DataStructures.Lists.IList<double> weights,
                                  Func<IEnumerable<KeyValuePair<int,double>>,IMap<int,double>> createMap = null  )
         {
             _values = values;
             createMap = createMap ?? (it => AlgoritmiaFactory.Maps<int, double>.BuildDefault(it));
             var dict = createMap(values.Select((e, i) => new KeyValuePair<int, double>(e, weights[i])));

             _weightingFunction = (state,d) => new ValueWithDecisionAndBackpointer<double, int>(dict[d],d);

             _solver = new IterativeIdempotentDynamicProgrammingSolver<int, int, ValueWithDecisionAndBackpointer<double,int>>();
             
         }

         public ValueWithDecisionAndBackpointer<double,int> Solve(int Q)
         {
             return _solver.Solve(new MoneyChangeBackwardsStateSpace(Q, _values),
                           MinTropicalBackpointerSemiRing<double, int>.GetInstance(), _weightingFunction);
         }
    }
}
